package cn.myworld.algorithm.opt;

/**
 * 快慢指针_中间值问题
 */
public class FastSlowPointer {
    public static void main(String[] args) {
        Node<String> first = new Node<String>("aa", null);
        Node<String> second = new Node<String>("bb", null);
        Node<String> third = new Node<String>("cc", null);
        Node<String> fourth = new Node<String>("dd", null);
        Node<String> fifth = new Node<String>("ee", null);
        Node<String> six = new Node<String>("ff", null);
//        Node<String> seven = new Node<String>("gg", null);

        // 节点之间的指向
        first.next = second;
        second.next = third;
        third.next = fourth;
        fourth.next = fifth;
        fifth.next = six;
//        six.next = seven;

        // 查找中间值
        String mid = getMid(first);
        System.out.println("中间值为：" + mid);
    }

    /**
     * @param first 链表的首节点
     * @return 链表中间节点的值
     */
    public static String getMid(Node<String> first) {
        // 定义两个指针
        Node<String> fast = first;
        Node<String> slow = first;
        // 使用两个指针遍历链表，当快指针指向的节点没有下一个节点了，就可以结束了，结束之后，慢指针指向的节点就是中间值
        while (fast != null && fast.next != null) {
            // 变化fast和slow的值
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow.data;
    }

    /**
     * 节点类
     */
    private static class Node<T> {
        T data;
        Node<T> next;
        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }
}
